#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define MAX 20
typedef int ElemType;

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} ListNode;

void InitList(ListNode *&head) //初始化单链表
{
    head = (ListNode *)malloc(sizeof(ListNode));
    head->next = NULL;
}

void CreateListR(ListNode *&L, ElemType a[], int n) //尾插法插入
{
    ListNode *r = L, *s;
    for (int i = 0; i < n; i++)
    {
        s = (ListNode *)malloc(sizeof(ListNode));
        s->data = a[i];
        r->next = s;
        r = s;
    }
    r->next = NULL;
}

void OutList(ListNode *L) //输出链表
{
    ListNode *p = L->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void DestoryList(ListNode *&L) //释放单链表
{
    ListNode *pre = L, *p = L->next;
    while (p != NULL)
    {
        free(pre);
        pre = p;
        p = pre->next;
    }
    free(pre);
}

void partitionList(ListNode *&L, ElemType e) //将单链表分为两部分
{
    // 如果链表为空或只有一个节点，无需分割
    if (L->next == NULL || L->next->next == NULL)
        return;
    ListNode *pre = L->next;           //指向cur前一个节点
    ListNode *current = L->next->next; // 从第二个节点开始遍历链表
    ListNode *small;
    while (current != NULL)
    {
        if (current->data >= e)
        {
            pre = pre->next;
            current = current->next;
        }
        else
        {
            small = current;
            pre->next = current->next;
            current = current->next;
            small->next = L->next;
            L->next = small;
        }
    }
}

int main()
{
    int count = 0; //统计元素个数
    int a[MAX];
    printf("请一次输入元素：（元素个数不超过20个，分隔符为空格，并且以-1作为结束输入标志）\n");
    scanf("%d", &a[0]);
    while (a[count] != -1)
    {
        count++;
        scanf("%d", &a[count]);
    }
    ListNode *L;
    InitList(L); //初始化链表，创建一个头节点
    CreateListR(L, a, count);
    printf("原始链表为：\n");
    OutList(L);

    printf("分割后的链表为：\n");
    partitionList(L, a[0]);
    OutList(L);
    DestoryList(L);

    return 0;
}

//测试数据1：5 5 5 5 6 4 -1    结果：4 5 5 5 5 6
//测试数据2：-1   结果：NULL
//测试数据3：2 -1  结果：2
